package zuochengyun;

import java.util.LinkedList;
import java.util.Queue;

//求最短路径值	P384
//带有障碍的最短路径值，即求迷宫的最短路径值
public class ObstacleShortPath {

	public static void main(String[] args) {
		ObstacleShortPath object = new ObstacleShortPath();
		int[][] m = {{1, 0, 1, 1},
					{1, 1, 1, 1},
					{1, 0, 0, 1},
					{1, 1, 1, 1}};
		System.out.println(object.minPathValue(m));
	}
	
	//0代表无法通过，1代表可以通过
	//从左上角走到右下角
	public int minPathValue(int[][] m){
		if(m == null || m.length <= 0 || m[0].length <= 0 || m[0][0] != 1 
				|| m[m.length - 1][m[0].length - 1] != 1){
			return 0;
		}
		int res = 0;
		final int rowLength = m.length;
		final int colLength = m[0].length;
		
		//map[i][j]的含义是从[0][0]走到[i][j]最短的路径值
		int[][] map = new int[rowLength][colLength];
		map[0][0] = 1;
		
		//生成两个队列来存储行和列
		Queue<Integer> rowQueue = new LinkedList<Integer>();
		Queue<Integer> colQueue = new LinkedList<Integer>();
		
		rowQueue.add(0);
		colQueue.add(0);
		int row = 0;
		int col = 0;
		while(!rowQueue.isEmpty() && !colQueue.isEmpty()){
			row = rowQueue.poll();
			col = colQueue.poll();
			
			//如果到达了最后的终点
			//由于是严格的加1，所以最后到达终点就是最小值
			if(row == rowLength - 1 & col == colLength - 1){
				return map[row][col];
			}
			walkTo(map[row][col], row - 1, col, m, map, rowQueue, colQueue);	//up
			walkTo(map[row][col], row + 1, col, m, map, rowQueue, colQueue);	//down
			walkTo(map[row][col], row, col - 1, m, map, rowQueue, colQueue);	//left
			walkTo(map[row][col], row, col + 1, m, map, rowQueue, colQueue);	//right
		}
		//如果没有到达终点，返回0
		return res;
	}
	
	public void walkTo(int pre, int toRowIndex, int toColIndex, int[][] m, int[][] map,
			Queue<Integer> rowQueue, Queue<Integer> colQueue){
		// map[toRowIndex][toColIndex] != 0表示之前已经处理过该结点
		if(toRowIndex < 0 || toRowIndex == m.length || toColIndex < 0 || toColIndex == m[0].length
				|| m[toRowIndex][toColIndex] == 0 || map[toRowIndex][toColIndex] != 0){
			return;
		}
		map[toRowIndex][toColIndex] = pre + 1;
		//将该点添加至队列
		rowQueue.add(toRowIndex);
		colQueue.add(toColIndex);
	}
}
